/*
 * Copyright (c) 2022  by Junzhao
 * THIS FILE IS PART OF JAVA-Data-Structures-and-Algorithms PROJECT
 * All Rights Reserved.
 */

package 单向环链表;

/**
 * @Description 约瑟夫问题另一种实现
 * 逻辑上相差无几
 * @Author 俊昭
 * @Date 2022/4/29
 */
public class Que2 {
    private static final Node first = new Node(- 1);

    /**
     * @param k 从第几个人开始
     * @param n 几个人围成圈
     * @param m 开始后数到m的人踢出，其下一位继续报m个数
     * @description
     * @author 俊昭
     * @date 2022/4/28
     */
    public static void pop(int n, int k, int m) {
        if (n < 1) {
            throw new RuntimeException("不可以小于一!");
        } else {
            Node temp = new Node(1);
            first.next = temp;
            for (int i = 0; i < n; i++) {
                if (i == n - 1) {
                    temp.next = first.next;
                } else {
                    temp.next = new Node(i + 2);
                    temp = temp.next;
                }
            }
        }

        Node temp = first;
        // 找到第k个人
        for (int i = 0; i < k; i++) {
            temp = temp.next;
        }


        if (m % n == 1) {
            // 直接顺序输出
            Node flag = temp;
            while (temp.next != flag) {
                System.out.println(temp.next);
                temp = temp.next;
            }
            System.out.println(temp.next);
        } else {
            // 报m-1下踢出 直到"圈上"只剩下一个为止
            while (first.next.next != first.next) {
                for (int i = 1; i < m; i++) {
                    if (i == m - 1) {
                        if (temp.next == first.next) {
                            //如果恰好移除了与辅助节点相连的节点就进行更换
                            first.next = temp;
                        }
                        System.out.println(temp.next);
                        temp.next = temp.next.next;
                    }
                    temp = temp.next;
                }
            }
            System.out.println(first.next);
        }

    }
}

class Que2Test {
    public static void main(String[] args) {
        Que2.pop(10, 2, 2);
        System.out.println();
        Que2.pop(5, 1, 2);
    }
}